#pragma once

#include <unordered_map>
#include <vector>

namespace jianzhi_007
{

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
};

class Solution
{
public:
    TreeNode* buildTree(const std::vector<int>& preorder,
                        const std::vector<int>& inorder)
    {
        if (preorder.empty() || inorder.empty())
            return nullptr;
        m_preorder = preorder;
        for (int i = 0; i < (int)inorder.size(); ++i)
            m_inorder.emplace(inorder.at(i), i);
        return build_subtree(0, 0, inorder.size() - 1);
    }

private:
    TreeNode* build_subtree(int pre, int in_left, int in_right)
    {
        if (in_left > in_right)
            return nullptr;

        auto root = new TreeNode(m_preorder.at(pre));
        int l_size = m_inorder.at(root->val) - in_left;
        root->left = build_subtree(pre + 1, in_left, m_inorder.at(root->val) - 1);
        root->right = build_subtree(pre + l_size + 1, m_inorder.at(root->val) + 1, in_right);
        return root;
    }

    std::vector<int> m_preorder;
    std::unordered_map<int, int> m_inorder;
};

}  /* namespace jianzhi_007 */
